%\vspace{-1.5mm}
\section{The FlexRay Dynamic segment}
\label{sec:basic_flex}
%\vspace{-1mm}

The FlexRay Communication protocol~\cite{FR} is organized as a periodic sequence of communication cycles with fixed length, $\flexrayCycleLength$. Each communication cycle is further subdivided into two a ST and a DYN segment. In this paper, we propose a timing analysis scheme for the DYN segment and hence, in the following we discuss the DYN segment.\\  

%In summary, the following are four notable properties of FlexRay dynamic segment.

%[FR1)] One minislot is consumed from the available service each time a task is not ready to transmit a message, before the next lower priority task is allowed to send its message on the DYN segment of the bus.	
%	[FR2)] A task can send at most one message in one DYN segment (where the maximum length of the message can be equal to 254~bytes~\cite{FR}).	
%[FR3)]If a DYN segment message is generated by its sender task after the slot has started, it will not be transmitted in that cycle.	
%[FR4)]A task is only allowed to send a message if it fits into the remaining portion of the current DYN segment, i.e., a message can not straddle two communication cycles.
%----------------------------------------------
\begin{figure}%[!ht]
\centering
\vspace{-10.5mm}
\includegraphics[width=1.7\columnwidth]{./figures/example}
\vspace{-6cm}
\caption{Example 1: Messages $m_1$ and $m_2$ are multiplexed in FlexRay DYN segment.}
\label{fig:example1}
\vspace{-5.5mm}
\end{figure}

%----------------------------------------------

\noindent \textbf{Dynamic Segment:} In FlexRay a set of $\flexrayMatrixLength$ communication cycles constitute a  pattern which is repeated. Each cycle is indexed by a \textit{cycle counter}. The cycle counter is incremented from $0$ to $\flexrayMatrixLength-1$ after which the cycle counter is reset to $0$. Figure~\ref{fig:example1}(a) illustrates a FlexRay communication pattern with $\flexrayMatrixLength = 4$. Each message to be transmitted over the FlexRay DYN segment is assigned two attributes that define the set of cycles between $0$ and $\flexrayMatrixLength-1$ where the message is allowed to be transmitted. These attributes for a message $m_i$ are (i) the base cycle or the starting cycle $B_i$ within $\flexrayMatrixLength$ communication cycles, and (ii) the cycle repetition rate $R_i$ which indicates the minimum length (in terms of the number of FlexRay cycles) between two consecutive allowable transmissions. As an example, let us consider three messages $m_1$, $m_2$ and $m_3$ to be transmitted over the FlexRay cycles in Figure~\ref{fig:example1}(a). Let the base cycles be $B_1=B_2=0$ and $B_3=1$ and let the repetition rates be set to $R_1=R_2=R_3=2$. Figure~\ref{fig:example1}(a) shows the cycles where $m_1$, $m_2$ and $m_3$ can be transmitted with these properties. In this example, $m_2$ and $m_3$ can be transmitted in cycle 0 and cycle 1 respectively. Thereafter, they can be transmitted every alternate cycle. The same priority is assigned to $m_2$ and $m_3$ and they are said to be slot multiplexed. According to the FlexRay standard, the base cycle $B_i \in [0...\flexrayMatrixLength-1]$, and $B_i < R_i$. The relation $B_i \in [0...\flexrayMatrixLength-1]$ holds true by definition. The relation $B_i < R_i$ is also enforced by the specification to ensure the definition of $R_i$ when it straddles two adjacent FlexRay cycles. % and the cycle counter $C_i = (B_i + n*R_i)_{mod64}$, $n\in[0,1,2....]$ \cite{FR, FRIF}.
  
Conflicts between messages to be sent in the same cycle are resolved using priorities as each message is assigned a fixed priority. Each DYN segment in FlexRay is partitioned into equal-length slots which are referred to as ``minislots". At the beginning of each DYN segment, the highest priority message gets access to the bus and it occupies the required number of minislots on the bus according to its size. However, if the message is not ready for transmission or the size of the message does not fit into the remaining portion of the DYN segment, then only one minislot goes empty. In either case, the bus is then given to the next highest-priority message and the same process is repeated until the end of the DYN segment. Further, at most one instance of each message is only allowed to be transmitted in each FlexRay cycle. In Figure~\ref{fig:example1}(b), the DYN segment in each FlexRay cycle consists of 8 minislots. $m_1$ is the highest priority message (priority 1) in cycle 2 and hence, occupies 5 minislots corresponding to its size. In cycle 3, however, there is no message with priority 1 that is ready and hence, one minislot is wasted before $m_3$ with priority 2 is transmitted.%In the following few paragraphs, the idea of 64-cycle matrix is explained from the perspective of the FlexRay dynamic segment, followed by two illustrative examples.

%The DYN segment consists of a configurable amount of minislots of fixed length (e.g., $MS$). Each minislot is numbered by a \textit{minislot counter}. The minislot counter counts the number of minislots from the beginning of the DYN segment. Furthermore, there is a \textit{slot counter} which counts the total number of communication slots available in a particular cycle (Figure \ref{fig:DYN2}). For example, if there are $i$ number of ST slots (or ST segment messages), the slot counter for DYN segment messages starts from $(i+1)$. 

%Any dynamic segment message $m_{i}$ uses three scheduling parameters to uniquely specify its transmission:  
 %According to the FlexRay communication protocol (, \cite{}), the following relations must hold among these three parameters for any message $m_i$:
%Cycle Repetition $R_i=2^R_i$; R $\in [0...6]$.

\begin{figure}%[!ht]
\centering
\includegraphics[width=1.0\columnwidth]{./figures/example2}
\vspace{-4.5mm}
\caption{Example 2: Messages $m_1$ and $m_3$ are never transmitted in same cycles, yet $m_1$ influences the transmission of $m_3$ indirectly.}
\label{fig:example2}
\vspace{-5.5mm}
\end{figure}

  
\section{Motivational Examples}
\label{sec:motivate}
With the help of two examples, we shall illustrate the need for new techniques, as proposed in this paper, for timing analysis of the DYN segment when slot multiplexing is allowed. First let us consider the example shown in Figure~\ref{fig:example1}(a). The size of the messages in terms of the minislots is 5MS (minislots) for $m_1$, 6~MS for $m_2$ and 3~MS for $m_3$. %The worst-case delay scenarios for the $m_2$ and $m_3$ occur when they are ready for transmission just after their minislots have passed. 
Let us consider the worst-case delay scenario for message $m_2$. Consider that $m_2$ is ready just after minislot 2 in cycle 0 and hence, it cannot be transmitted in cycle 0. With $B_2=0$ and $R_2=2$, $m_2$ cannot be transmitted in cycle 1. Let us assume that $m_1$ is ready now and is transmitted in cycle 2. Thereafter, $m_1$ occupies 5~MS the DYN segment has 3~MS left. Thus, $m_2$ cannot fit into cycle 2. Again, $m_2$ is not allowed to be transmitted in cycle 3. Finally, $m_2$ is transmitted in cycle 0 in the next round. Thus, $m_2$ is delayed more than $4$ FlexRay cycles but less than 5 FlexRay cycles.  On the other hand, in the worst-case scenario, $m_3$ just misses its minislot in cycle 1 and is transmitted in cycle 3. Thus, $m_3$ is delayed less than $2$ FlexRay cycles.

From the above example, first, we note that both $m_2$ and $m_3$ have the same priority and yet they have completely different worst-case delays. Secondly, we emphasize that  the approach proposed by Schneider et. al.~\cite{SchneiderBGC10,Schneider2011} would report that $m_2$ and $m_3$ would suffer from infinite delays because they are delayed more than one FlexRay cycle. Thus, their approach would report that the given message set is unschedulable. However, as we have seen in this example, $m_2$ and $m_3$ have finite delays and are actually schedulable for any values of deadlines that span more than the length of 5 and 2 FlexRay cycles.

Let us now consider a second example as shown in Figure~\ref{fig:example2}(a). Compared to Figure~\ref{fig:example1}(a), $m_3$'s priority is now 3 and $m_2$ now has $R_2=1$. Thus, $m_2$ and $m_3$ now have conflicts in cycles 1 and 3. Rest of the values remain the same as in Figure~\ref{fig:example1}(a). Note that $m_1$ and $m_3$ have no cycles in common. However, $m_1$ might delay $m_2$ and that might lead to delaying of $m_3$. Hence, techniques that have not considered slot multiplexing~\cite{Andrei07,ZengGN10,PPEPA08,SchmidtS10a}, will not be able to report accurate results. In order to provide safe results, such techniques would have to assume that  the message $m_1$ is allowed to be transmitted in every cycle and this would lead to very pessimistic results.

  
\section{System Model}
\label{sec:systemModel}

We assume that the set of messages $\msgset$ that will be transmitted on the FlexRay DYN segment is known. Any message $m_i \in \msgset$, is associated with the following properties. 
\begin{enumerate}
	\item The period $\messagePeriod_i$ that denotes the rate at which $m_i$ is being produced.
	\item The deadline $\messageDeadline_i$, of a message $m_i$ is the relative time since the production of $M_i$ until the time by which the transmission of $m_i$ must end.
	\item The repetition rate $R_i$, and the base cycle $B_i$ for each message $m_i$, as defined in Section \ref{sec:basic_flex}, is assumed to be known.
        \item The size of the message $\messageSize_i$ in terms of the number of minislots that the message $m_i$ would occupy when transmitted on the DYN segment.
        \item The priority $\messagePriority_i$ of each message $m_i$ that is used to resolve bus access contentions as discussed in Section \ref{sec:basic_flex}, is assumed to be known. A higher value of the priority implies a lower priority.
\end{enumerate}

We assume that the FlexRay cycle length is $\flexrayCycleLength$.  The length of one minislot is denoted $\minislotLength$, and the total number of minislots $\numberOfMinislots$ is considered to be given. The length of the DYN segment is thus $\flexrayDYNLength=\minislotLength \times \numberOfMinislots$. Assuming that the length of the ST is $\flexraySTLength$, FlexRay cycle length is $\flexrayCycleLength = \flexraySTLength + \flexrayDYNLength$.
%		\item The message under analysis $m_a$ is considered.
%\item A set of high priority messages $hp(m_a) = \{m_1, m_2, \cdots, m_N \}$. 
%	\end{itemize}